package algorithm.recurrence;

import sun.security.krb5.internal.PAData;

/**
 * 杨辉三角
 *
 * @author 杨 强
 * @package algorithm.recurrence
 * @createTime 2023-03-08 23:00
 */
public class YangHui {
    public static void main(String[] args) {
        // 求坐标的值
//        System.out.println(element(3, 2));
        print2(10);
    }


    /**
     * 双重循环打印, , 优化版本
     * 打印n高度的杨辉三角
     * @param n 三角形的高度
     */
    private static void print2(int n){
        // 定义一个二维数组来存左边的值, 二维数组的一维长度可以确定,就是n, 但是二维数组的长度是动态的变化的,我们就动态的为一维数组的二维数组初始大小
        int[][] array = new int[n][];

        for (int i = 0; i < n; i++) {
            // 为一维数组的二维数组初始化大小
            array[i] = new int[i + 1];

            // 打印每一行的空格, 让角行摆正
            printEmpty(n, i);

            // 循环打印一列值
            for (int j = 0; j <= i ; j++) {
                // 打印当前坐标的值
                System.out.print("   " + element2(array, i, j));
            }
            // 打印完一行后就换行
            System.out.println();
        }
    }

    /**
     * 求出指定行列位置的数字的值, 优化版本
     * @param array 缓存值的数组
     * @param i X坐标
     * @param j Y坐标
     * @return
     */
    private static int element2(int[][] array, int i, int j){
        // 当坐标在数组中有值,那么就返回数组坐标中的值
        if (array[i][j] > 0){
            return array[i][j];
        }

        // 这个情况就是两边等于1的边的左边值
        if (j == 0 || i == j){
            array[i][j] = 1;
            return array[i][j];
        }

        // 把坐标的值存入数组
        array[i][j] = element2(array, i -1, j - 1) + element2(array, i -1, j);

        // 返回坐标值
        return array[i][j];
    }


    /**
     * 双重循环打印
     * 打印n高度的杨辉三角
     * @param n 三角形的高度
     */
    private static void print(int n){
        for (int i = 0; i < n; i++) {
            // 打印每一行的空格, 让角行摆正
            printEmpty(n, i);
            for (int j = 0; j <= i ; j++) {
                // 打印当前坐标的值
                System.out.print("   " + element(i, j));
            }
            // 打印完一行后就换行
            System.out.println();
        }
    }

    /**
     * 求出指定行列位置的数字的值
     * @param i X坐标
     * @param j Y坐标
     * @return
     */
    private static int element(int i, int j){
        if (j == 0 || i == j){
            return 1;
        }

        return element(i -1, j - 1) + element(i -1, j);
    }


    /**
     * 每一行打印空格,让杨辉三角摆正
     * 这个需要求规律, 当我们的数字之间隔4个空格的时候, 那么下面就是*2
     * 每一行应该打印的空格的公式是: (n - 1 - i) * 2
     */
    private static void printEmpty(int n, int i){
        int num = (n - 1 - i) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

}
